package main

import (
	"fmt"
	"math/rand"
	"runtime"
	"time"
)

func geraMatrizAleatoria2D(lin, col int) [][]int {
	matriz := make([][]int, lin)
	for i := 0; i < lin; i++ {
		matriz[i] = make([]int, col)
		for j := 0; j < col; j++ {
			matriz[i][j] = rand.Intn(9)
		}
	}
	return matriz
}

func multiplicaMatrizes(matriz1, matriz2 [][]int) [][]int {
	linMult := len(matriz1)
	colsMult := len(matriz2[0])
	dimComum := len(matriz1[0])
	mult := make([][]int, linMult)
	for i := 0; i < linMult; i++ {
		mult[i] = make([]int, colsMult)
		for j := 0; j < colsMult; j++ {
			mult[i][j] = 0
			for k := 0; k < dimComum; k++ {
				mult[i][j] += matriz1[i][k] * matriz2[k][j]
			}
		}
	}
	return mult
}

func somaMatrizes(matriz1, matriz2 [][]int) [][]int {

	linMult := len(matriz1)
	colsMult := len(matriz2[0])
	mult := make([][]int, linMult)

	for i := 0; i < linMult; i++ {
		mult[i] = make([]int, colsMult)
		for j := 0; j < colsMult; j++ {
			mult[i][j] += matriz1[i][j] + matriz2[i][j]
		}
	}

	return mult

}

func printMatriz(nome string, m [][]int) {
	fmt.Printf("%s = [\n", nome)
	for i := 0; i < len(m); i++ {
		for j := 0; j < len(m[0]); j++ {
			fmt.Printf("%d ", m[i][j])
		}
		fmt.Println()
	}
	fmt.Println("]")
}

func multiplicaMatrizesBlocos(matriz1, matriz2 [][]int, nCore int) [][]int {

	halfM := len(matriz1) / 2

	a := make([][]int, halfM)
	b := make([][]int, halfM)
	c := make([][]int, halfM)
	d := make([][]int, halfM)

	e := make([][]int, halfM)
	f := make([][]int, halfM)
	g := make([][]int, halfM)
	h := make([][]int, halfM)

	for bloc := 0; bloc <= halfM; bloc += halfM {
		m := make([][]int, halfM)
		for i := 0; i < halfM; i++ {
			m[i] = make([]int, halfM)
			for j := 0 + bloc; j < halfM+bloc; j++ {
				m[i][j-bloc] = matriz1[i][j]
			}
		}

		n := make([][]int, halfM)
		for i := halfM; i < halfM*2; i++ {
			n[i-halfM] = make([]int, halfM)
			for j := 0 + bloc; j < len(matriz1)/2+bloc; j++ {
				n[i-halfM][j-bloc] = matriz1[i][j]
			}
		}

		if bloc == 0 {
			a = m
			c = n
		} else {
			b = m
			d = n
		}
	}

	for bloc := 0; bloc <= halfM; bloc += halfM {
		m := make([][]int, halfM)
		for i := 0; i < halfM; i++ {
			m[i] = make([]int, halfM)
			for j := 0 + bloc; j < halfM+bloc; j++ {
				m[i][j-bloc] = matriz2[i][j]
			}
		}

		n := make([][]int, halfM)
		for i := halfM; i < halfM*2; i++ {
			n[i-halfM] = make([]int, halfM)
			for j := 0 + bloc; j < len(matriz2)/2+bloc; j++ {
				n[i-halfM][j-bloc] = matriz2[i][j]
			}
		}

		if bloc == 0 {
			e = m
			g = n
		} else {
			f = m
			h = n
		}
	}

	mult := mutiplicacaoPorRotinas(a, b, c, d, e, f, g, h)

	return mult

}

func mutiplicacaoPorRotinas(a, b, c, d, e, f, g, h [][]int) [][]int {

	linMat := len(a)
	cn := make(chan bool, 4)

	b1 := make([][]int, linMat)
	go func() {
		ae := multiplicaMatrizes(a, e)
		bg := multiplicaMatrizes(b, g)
		b1 = somaMatrizes(ae, bg)
		cn <- true
	}()

	b2 := make([][]int, linMat)
	go func() {
		af := multiplicaMatrizes(a, f)
		bh := multiplicaMatrizes(b, h)
		b2 = somaMatrizes(af, bh)
		cn <- true
	}()

	b3 := make([][]int, linMat)
	go func() {
		ce := multiplicaMatrizes(c, e)
		dg := multiplicaMatrizes(d, g)
		b3 = somaMatrizes(ce, dg)
		cn <- true
	}()

	b4 := make([][]int, linMat)
	go func() {
		cf := multiplicaMatrizes(c, f)
		dh := multiplicaMatrizes(d, h)
		b4 = somaMatrizes(cf, dh)
		cn <- true
	}()

	for i := 0; i < 4; i++ {
		<-cn
	}

	matriz := mesclaMatriz(b1, b2, b3, b4)

	return matriz
}

func mesclaMatriz(b1, b2, b3, b4 [][]int) [][]int {

	linMat := len(b1)
	matriz := make([][]int, linMat*2)

	for i := 0; i < linMat; i++ {
		matriz[i] = make([]int, linMat*2)
		matriz[i+linMat] = make([]int, linMat*2)
		for j := 0; j < linMat; j++ {
			matriz[i][j] = b1[i][j]
			matriz[i][j+linMat] = b2[i][j]
			matriz[i+linMat][j] = b3[i][j]
			matriz[i+linMat][j+linMat] = b4[i][j]
		}
	}

	return matriz
}

func main() {

	var tamMat, nCore int

	// entrando com o número de processadores
	fmt.Println("Multiplicador de Matrizes")
	fmt.Printf("Digite o número de núcleos (max: %d):", runtime.NumCPU())
	fmt.Scan(&nCore)

	// estabelecendo o número de processadores
	runtime.GOMAXPROCS(nCore)

	// tamanho da matriz quadrada
	// *********************************************************
	// (solução somente para matriz quadrada de número par)
	// *********************************************************
	fmt.Printf("Digite o tamanho da matriz quadrada:")
	fmt.Scan(&tamMat)

	if tamMat%2 > 0 {
		tamMat--
	}

	fmt.Println("Multiplicador de Matrizes")
	fmt.Printf("  Máximo %d processadores\n", runtime.NumCPU())
	linM1 := tamMat
	colsM1 := tamMat
	linM2 := colsM1
	colsM2 := tamMat

	matriz1 := geraMatrizAleatoria2D(linM1, colsM1)
	//printMatriz("matriz1", matriz1)
	matriz2 := geraMatrizAleatoria2D(linM2, colsM2)
	//printMatriz("matriz2", matriz2)

	start := time.Now()
	elapsedA := time.Since(start)
	if nCore == 1 {
		multM1M2 := multiplicaMatrizes(matriz1, matriz2)
		//printMatriz("multiplicacao", multM1M2)
		elapsedA = time.Since(start)
		
		fmt.Println(multM1M2[0][0])
	} else {
		elapsedA = 0
		fmt.Println("Serial não executada!")
	}

	start = time.Now()
	multM1M2B := multiplicaMatrizesBlocos(matriz1, matriz2, nCore)
	elapsedB := time.Since(start)

	//printMatriz("multiplicacao", multM1M2B)
	fmt.Println("tempo serial = ", elapsedA)
	fmt.Println("tempo por blocos = ", elapsedB)
	fmt.Println("tamanho da matriz = ", tamMat)
	fmt.Println("qtde processadores ", nCore)
	
	fmt.Println(multM1M2B[0][0])

}
